package dp;

/**
 * 最长公共子序列
 *
 * @author zj
 */
public class LongestCommonSubsequence {
    public static void main(String[] args) {
        int arr1[] = {'z', 'x', 'y', 'x', 'y', 'z', 'x'}; //{1, 3, 5, 2, 7, 6, 9};
        int arr2[] = {'x', 'y', 'y', 'z', 'x'}; //{2, 3, 5, 6, 7, 9};
        System.out.println(solution(arr1, arr2));
    }

    public static int solution(int[] arr1, int[] arr2) {
        if (arr1 == null || arr2 == null || arr1.length == 0
                || arr2.length == 0) {
            return 0;
        }
        int tmp[][] = new int[arr1.length + 1][arr2.length + 1];
        //边界条件
        for (int i = 0; i <= arr1.length; i++) {
            tmp[i][0] = 0;
        }
        for (int j = 0; j <= arr2.length; j++) {
            tmp[0][j] = 0;
        }
        int max = 0;
        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                //由于tmp[0][0]表示的是两个序列都不存在元素，所以这里tmp[i][j]对应的是arr1[i-1]和arr2[j-1]的比较
                if (arr1[i - 1] == arr2[j - 1]) {
                    tmp[i][j] = tmp[i - 1][j - 1] + 1;
                } else {
                    tmp[i][j] = Math.max(tmp[i - 1][j], tmp[i][j - 1]);
                }
                max = Math.max(max, tmp[i][j]);
            }
        }
        return max;
    }
}
